package src.tree;

import java.util.ArrayDeque;
import java.util.ArrayList;

public class no513 {//找树左下角的值

    //层序遍历，收集每层的第一个值，最终拿list中的最后一个
    public int findBottomLeftValue(TreeNode root) {
        if (root == null) return -1;
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        //ArrayList<Integer> list = new ArrayList<>();
        //或者不用list，只用一个变量存，每层中覆盖这个值
        int res = 0;
        queue.add(root);

        while (!queue.isEmpty()) {
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                //if (i == 0) list.add(node.val);
                if (i == 0) res = node.val;

                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
        }
        //return list.get(list.size() - 1);
        return res;

    }

    public int findBottomLeftValue2(TreeNode root) {
        if (root == null) return -1;
        dfs(root, 1);
        return res;

    }

    int maxDepth = 0;
    int res = 0;

    void dfs(TreeNode root, int depth) {
        if (root == null) return;
        if (root.left == null && root.right == null) {
            //每次更新树高，保证maxDepth是最下层，然后记录node.val
            if (depth > maxDepth) {
                maxDepth = depth;
                res = root.val;
            }
            return;
        }
        //找最大深度
        if (root.left != null) {
            dfs(root.left, depth + 1);
/*            depth++;
            dfs(root.left, depth);
            depth--;  //回溯*/
        }
        if (root.right != null) {
            dfs(root.right, depth + 1);
/*            depth++;
            dfs(root.right, depth);
            depth--;  //回溯*/
        }
        return;
    }

}
